// O(n) 的时间复杂度
var myPow = function (x, n) {
  let value = 0;
  let res = 1;
  while (value < Math.abs(n)) {
    value++;
    res = res * x;
  }

  if (n >= 0) {
    return res;
  } else {
    return 1 / res;
  }
};

// O(logn)的时间复杂度
//  利用递归的方式进行优化
var myPow = function (x, n) {
  let res = 1;

  function dfs(value, index) {
    if (index == 1) {
      return value;
    }

    if (index == 0) {
      return 1;
    }

    if (index % 2 == 1) {
      let data = dfs(value, Math.floor(index / 2));
      return value * data * data;
    } else {
      let data = dfs(value, index / 2);
      return data * data;
    }
  }

  res = dfs(x, Math.abs(n));

  if (n >= 0) {
    return res;
  } else {
    return 1 / res;
  }
};
